//分割回文串Ⅱ
class Solution {
public:
    int minCut(string s) {
        //先把所有字符串是否回文的信息保存起来
        int n = s.size();
        vector<vector<bool>> memo(n , vector<bool>(n));
        for(int i = n - 1 ; i >= 0 ; --i)
        {   
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                {
                    if(i == j) memo[i][j] = true;
                    else if(i + 1 == j) memo[i][j] = true;
                    else memo[i][j] = memo[i+1][j-1];
                }
            }
        }

        vector<int> dp(n);
        for(int i = 0 ; i < n ; ++i)
        {
            if(memo[0][i]) dp[i] = 0;
            else 
            {
                bool is = false;
                for(int j = 1 ; j <= i ; ++j)
                {
                    if(memo[j][i])
                    {
                        if(!is)
                        {
                            is = true;
                            dp[i] = dp[j-1]+1;
                        }
                        else dp[i] = min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return dp[n-1];
    }
};

//最长回文子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n,1));
        //状态表示：s字符串中[i,j]区间内的最长回文子序列的长度
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j])
                {
                    if(i == j) dp[i][j] = 1;
                    else if(i+1 == j) dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1] + 2;
                }
                else 
                {
                    dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};

//让字符串成为回文串的最少插入次数
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        for(int i = n-1 ; i >= 0 ; --i)
        {
            for(int j = i ; j < n ; ++j)
            {
                if(s[i] == s[j]) 
                {
                    if(i == j) dp[i][j] = 0;
                    else if(i + 1 == j) dp[i][j] = 0;
                    else dp[i][j] = dp[i+1][j-1];
                }
                else 
                {
                    if(i + 1 == j) dp[i][j] = 1;
                    else dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;
                }
            }
        }
        return dp[0][n-1];
    }
};